home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 13131 < prev    next >
Encoding:
Text File  |  1996-08-05  |  2.7 KB  |  75 lines
  1. Newsgroups: comp.lang.misc,comp.lang.c,gnu.gcc
  2. Path: news.ifm.liu.se!liuida!ricwe
  3. From: ricwe@ida.liu.se (Rickard Westman)
  4. Subject: GCC optimizes tail calls? (was: GOTO controversy)
  5. X-Nntp-Posting-Host: sen21.ida.liu.se
  6. Message-ID: <DpCt69.8I0@ida.liu.se>
  7. Followup-To: comp.lang.misc
  8. Sender: news@ida.liu.se
  9. Organization: CIS Dept, Univ of Linkoping, Sweden
  10. References: <314FB5F5.259B@simi.is> <AD87DB279668D9F74@mcdiala15.it.luc.edu> <828549619snz@genesis.demon.co.uk> <oun34tm3c7.fsf@lynx.cs.byu.edu>
  11. Date: Thu, 4 Apr 1996 20:06:08 GMT
  12.  
  13. In article <oun34tm3c7.fsf@lynx.cs.byu.edu>,
  14. Kelly Hall <hall@cs.byu.edu> wrote:
  15. >>>>>> "Lawrence" == Lawrence Kirby <fred@genesis.demon.co.uk> writes:
  16. >    Lawrence> An O(log N) stack depth is generally not a problem. I
  17. >    Lawrence> guess you could say that is finite because there are
  18. >    Lawrence> typically practical upper bounds to N.
  19. >
  20. >Tail recursion is implemented by all non-stupid compilers the same way
  21. >as the imperative (goto) version.  Gcc will do this, whether or not
  22. >your favorite compiler will is a different matter.
  23. >
  24. >No stack problems at all.
  25.  
  26. I have seen several people claim that GCC does proper optimization
  27. of tail calls, but also claims to the contrary.  I decided to test
  28. it for myself with this little tail recursive program:
  29.  
  30.   #include <stdlib.h>
  31.   #include <stdio.h>
  32.   
  33.   int evenp(long i)
  34.   {
  35.     if (i==0) return 1;
  36.     return oddp(i-1);
  37.   }
  38.   
  39.   int oddp(long i)
  40.   {
  41.     if (i==0) return 0;
  42.     return evenp(i-1);
  43.   }
  44.   
  45.   int main(int argc, const char *argv[])
  46.   {
  47.     if (argc!=2) 
  48.       puts("Usage: oddp <number>");
  49.     else if (oddp(abs(atol(argv[1]))))
  50.       puts("Number is odd.");
  51.     else
  52.       puts("Number is not odd.");
  53.     return 0;
  54.   }
  55.  
  56. The sad truth is that this program, compiled with GCC 2.7.0 (-O3),
  57. blows the stack when tested with a number large enough.  Tail calls
  58. within a single function seems to be optimized, though, but this
  59. limitation is really too restrictive for people who want to program
  60. in a functional style (or translate functional programs to C.)
  61.  
  62. On the other hand, Suns unbundled C compiler (v3.0.1) seems to
  63. handle this example well, as well as mutual recursion between
  64. different compilation units.  The DEC OSF/1 compiler (v3.11 on an
  65. Alpha) also does OK, but only within a single compilation unit.
  66. More data points?
  67.  
  68. All in all, I don't think it's wise to count on tail call
  69. optimization if you are aiming for portable C code.
  70. --
  71. Rickard Westman                   |   "Beware of the panacea peddlers:
  72. Dept. of Computer Science         |    Just because you wind up naked 
  73. Link÷ping University              |    doesn't make you an emperor."  
  74. Sweden                            |              - Michael A Padlipsky
  75.